package com.gitee.wsl.mathematics.geometry.d2.contour.util

import com.gitee.wsl.mathematics.function.Scalars
import com.gitee.wsl.mathematics.geometry.d2.contour.region.Region2
import com.gitee.wsl.mathematics.geometry.d2.contour.ring.Ring2
import com.gitee.wsl.mathematics.geometry.d2.curve.CurveShape2d
import com.gitee.wsl.mathematics.vector.ext.approx
import com.gitee.wsl.mathematics.vector.vec2.Vec2f


object Split {
    fun split(a: Region2, b: Region2): Result {
        val queues = arrayOf<SweepQueue<CurveShape2d>>(SweepQueue(), SweepQueue())
        addToQueue(a, queues[0])
        addToQueue(b, queues[1])
        val union = VertexUnion()
        val intersections = mutableMapOf<CurveShape2d, DoubleAccumulator>()
        val cs = arrayOfNulls<CurveShape2d>(2)
        while (true) {
            val idx = SweepQueue.next(*queues)
            cs[idx] = queues[idx].take()
            if (cs[idx] == null) {
                break
            }
            intersections[cs[idx]?:error("null")] = DoubleAccumulator()
            for (c in queues[1 - idx].active()) {
                cs[1 - idx] = c
                val ts = cs[0]!!.intersections(cs[1]!!)
                for (i in ts.indices) {
                    val t0 = ts[i].x.toDouble()
                    val t1 = ts[i].y.toDouble()
                    intersections[cs[0]]?.add(t0)
                    intersections[cs[1]]?.add(t1)
                    val p0 = cs[0]!!.position(t0)
                    val p1 = cs[1]!!.position(t1)
                    union.join(p0, p1)
                }
            }
        }
        val deduped = intersections.mapValues { (c , acc) -> dedupe(c, acc, union) }
        return Result(split(a, deduped, union), split(b, deduped, union), union.roots())
    }

    private fun split(
        region: Region2,
        splits: Map<CurveShape2d, DoubleAccumulator>,
        union: VertexUnion
    ): Region2 = Region2(region.rings.mapNotNull { ring -> split(ring, splits, union) }.toTypedArray())

    private fun dedupe(
        c: CurveShape2d,
        acc: DoubleAccumulator,
        union: VertexUnion
    ): DoubleAccumulator {
        val ts = acc.toArray()
        ts.sort()
        val result = DoubleAccumulator()
        for (i in ts.indices) {
            val t0 = if (result.size() == 0) 0.0 else result.last()
            val t1 = ts[i]
            if (Scalars.equals(t0, t1, Intersections.PARAMETRIC_EPSILON)
                || (c.position(t0) approx c.position(t1))
            ) {
                union.join(c.position(t0), c.position(t1))
            } else if (Scalars.equals(t1, 1.0, Intersections.PARAMETRIC_EPSILON)
                || (c.position(t1) approx c.end())
            ) {
                union.join(c.position(t1), c.end())
            } else {
                result.add(t1)
            }
        }
        return result
    }

    private fun split(
        r: Ring2,
        splits: Map<CurveShape2d, DoubleAccumulator>,
        union: VertexUnion
    ): Ring2? {
        val curves = mutableListOf<CurveShape2d>()
        for (c in r.curves) {
            val acc = splits[c]!!
            for (cp in c.split(acc.toArray())) {
                val cpa = union.adjust(cp)
                if (cpa != null) {
                    curves.add(cpa)
                }
            }
        }
        return if (curves.size == 0) null else Ring2(curves)
    }

    private fun addToQueue(region: Region2, queue: SweepQueue<CurveShape2d>) {
        for (r in region.rings) {
            for (c in r.curves) {
                // TODO EJ: determine if taking the extends of the bounding box of the curve is the better solution
                queue.add(c, c.start().x.toDouble(), c.end().x.toDouble())
//                val bounds = c.bounds()
//                if (!c.isFlat(SPATIAL_EPSILON)) {
//                    val cs = c.split(c.inflections())
//                    for (s in cs) {
//                        queue.add(s, s.bounds().lower().x, s.bounds().upper().x)
//                    }
//                } else {
//                    queue.add(c, bounds.lower().x, bounds.upper().x)
//                }

            }
        }
    }

    internal class VertexUnion {
        private val parent = mutableMapOf<Vec2f, Vec2f>()
        private val roots = mutableSetOf<Vec2f>()
        fun join(a: Vec2f, b: Vec2f) {
            @Suppress("NAME_SHADOWING") var a: Vec2f = a
            @Suppress("NAME_SHADOWING") var b: Vec2f = b
            a = adjust(a)
            b = adjust(b)
            val cmp = a.compareTo(b)
            when {
                cmp < 0 -> {
                    parent[b] = a
                    roots.add(a)
                }
                cmp > 0 -> {
                    parent[a] = b
                    roots.add(b)
                }
                else -> {
                    roots.add(b)
                }
            }
        }

        fun adjust(p: Vec2f): Vec2f {
            var curr = p
            while (true) {
                val next = parent[curr]
                if (next == null) {
                    if (curr != p) {
                        parent[p] = curr
                    }
                    return curr
                }
                curr = next
            }
        }

        fun adjust(c: CurveShape2d): CurveShape2d? {
            val start = adjust(c.start())
            val end = adjust(c.end())
            return if (start == end) null else c.endpoints(start, end)
        }

        fun roots(): Set<Vec2f> {
            return (roots - parent.keys)
        }
    }
    class Result(val a: Region2, val b: Region2, val splits: Set<Vec2f>)
}

